DC/LC analysis of Keccak-f[100]
Linear cryptanalysis

1 trails of length 2 read and checked.
1 trails of length 3 read and checked.
1 trails of length 4 read and checked.
1 trails of length 5 read and checked.
1 trails of length 6 read and checked.
Minimum weight: 8
       1 trails of weight  8
       1 trails of weight 20
       1 trails of weight 38
       1 trails of weight 66
       1 trails of weight 94

Showing the trails up to weight 94 (in no particular order).

2-round linear trail core of total weight 8
* Profile related to χ:
Propagation weights:    4   4
Active rows:                2
* Profile related to θ:
Gaps:          0
Kernel:        k
Round 0 would have weight at least 4
Round 1 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
....X   .....   .....   .....  |  .....   .....   .....   X....  |  .....   .....   .....   X....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
X.+..   .....   .....   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   X....  |  .....   .....   .....   X....
                                  -----   -----   -----   -----

3-round linear trail core of total weight 20
* Profile related to χ:
Propagation weights:    8   8   4
Active rows:                4   2
* Profile related to θ:
Gaps:          0   0
Kernel:        k   k
Round 0 would have weight at least 8
Round 1 (weight 8) after previous χ, then before θ of gap 0, then before χ (4 active rows):
.....   ..X..   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   X....   .....   .....  |  .....   X....   .....   .....  |  .....   X....   .....   .....
..+..   .....   .....   .....  |  ..+X.   .....   .....   .....  |  ..+X.   .....   .....   .....
...X.   .....   .....   .....  |  .....   X....   .....   .....  |  .....   X....   .....   .....
.....   .X...   .....   .....  |  ...X.   .....   .....   .....  |  ...X.   .....   .....   .....
                                  -----   -----   -----   -----
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   X....   .....   .....  |  ..XX.   .....   .....   .....  |  ..XX.   .....   .....   .....
..+X.   .....   .....   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   .....   .....
.....   X....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
...X.   .....   .....   .....  |  ..XX.   .....   .....   .....  |  ..XX.   .....   .....   .....
                                  -----   -----   -----   -----

4-round linear trail core of total weight 38
* Profile related to χ:
Propagation weights:   16   8   6   8
Active rows:                4   3   3
* Profile related to θ:
Gaps:          1   0   0
Kernel:        N   k   k
Round 0 would have weight at least 16
Round 1 (weight 8) after previous χ, then before θ of gap 1, then before χ (4 active rows):
.....   .....   .....   .....  |  .X...   .....   ..X..   .....  |  .....   .....   .....   .....
...X.   ..XXX   .....   .....  |  .X...   .X...   ..X..   .....  |  .....   .X...   .....   .....
..+..   .....   .XX..   .....  |  .X+..   XX...   ..X..   .....  |  ..+..   XX...   .....   .....
.X...   .....   .....   X...X  |  .X...   .....   ...X.   .....  |  .....   .....   ..XX.   .....
..X..   .....   ...X.   ..X..  |  .....   .....   ..X..   .....  |  .X...   .....   .....   .....
                                  -----   O----   ---O-   -----
Round 2 (weight 6) after previous χ, then before θ of gap 0, then before χ (3 active rows):
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   X....   .....   .....  |  ..+.X   .....   .....   .....  |  ..+.X   .....   .....   .....
.....   .....   ..X..   .....  |  X...X   .....   .....   .....  |  X...X   .....   .....   .....
.X...   .....   .....   .....  |  X....   .....   .....   .....  |  X....   .....   .....   .....
                                  -----   -----   -----   -----
Round 3 (weight 8) after previous χ, then before θ of gap 0, then before χ (3 active rows):
.....   .....   .....   .....  |  .....   .X..X   .....   .....  |  .....   .X..X   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+.X   .....   .....   .....  |  ..+..   .X...   .....   .....  |  ..+..   .X...   .....   .....
....X   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
X.X..   .....   .....   .....  |  .....   ....X   .....   .....  |  .....   ....X   .....   .....
                                  -----   -----   -----   -----

5-round linear trail core of total weight 66
* Profile related to χ:
Propagation weights:   12   8   4  22  20
Active rows:                2   2  10   8
* Profile related to θ:
Gaps:          0   0   2   0
Kernel:        k   k   N   k
Round 0 would have weight at least 12
Round 1 (weight 8) after previous χ, then before θ of gap 0, then before χ (2 active rows):
X....   .....   .X...   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   .X...   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   .....   .....
.....   X....   .....   .....  |  .XX.X   .....   .....   .....  |  .XX.X   .....   .....   .....
.....   .....   .....   X....  |  .XX.X   .....   .....   .....  |  .XX.X   .....   .....   .....
                                  -----   -----   -----   -----
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....   .....   .....   .....  |  .....   .X...   .....   .....  |  .....   .X...   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   .....   .....  |  ..+..   .X...   .....   .....  |  ..+..   .X...   .....   .....
....X   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..X..   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
                                  -----   -----   -----   -----
Round 3 (weight 22) after previous χ, then before θ of gap 2, then before χ (10 active rows):
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
..+..   .X...   .....   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   ..XX.   XX...
.....   .....   .....   .....  |  .....   .....   .....   .XX..  |  .....   .....   ..XX.   X.X..
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
                                  -----   -----   -----   -OO--
Round 4 (weight 20) after previous χ, then before θ of gap 0, then before χ (8 active rows):
.....   .....   ..X..   X.X..  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .....   ..X..   X....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   ..X..   X....  |  ..+.X   ...X.   X.XX.   .X...  |  ..+.X   ...X.   X.XX.   .X...
.....   .....   ..X..   XX...  |  .....   ...X.   .....   .....  |  .....   ...X.   .....   .....
.....   .....   ..X..   X....  |  ....X   .....   X.XX.   .X...  |  ....X   .....   X.XX.   .X...
                                  -----   -----   -----   -----

6-round linear trail core of total weight 94
* Profile related to χ:
Propagation weights:   12   8   4  22  20  28
Active rows:                2   2  10   8  12
* Profile related to θ:
Gaps:          0   0   2   0   1
Kernel:        k   k   N   k   N
Round 0 would have weight at least 12
Round 1 (weight 8) after previous χ, then before θ of gap 0, then before χ (2 active rows):
X....   .....   .X...   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   .X...   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   .....   .....
.....   X....   .....   .....  |  .XX.X   .....   .....   .....  |  .XX.X   .....   .....   .....
.....   .....   .....   X....  |  .XX.X   .....   .....   .....  |  .XX.X   .....   .....   .....
                                  -----   -----   -----   -----
Round 2 (weight 4) after previous χ, then before θ of gap 0, then before χ (2 active rows):
.....   .....   .....   .....  |  .....   .X...   .....   .....  |  .....   .X...   .....   .....
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   .....   .....  |  ..+..   .X...   .....   .....  |  ..+..   .X...   .....   .....
....X   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..X..   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
                                  -----   -----   -----   -----
Round 3 (weight 22) after previous χ, then before θ of gap 2, then before χ (10 active rows):
.....   .X...   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
..+..   .X...   .....   .....  |  ..+..   .....   .....   .....  |  ..+..   .....   ..XX.   XX...
.....   .....   .....   .....  |  .....   .....   .....   .XX..  |  .....   .....   ..XX.   X.X..
.....   .....   .....   .....  |  .....   .....   .....   .....  |  .....   .....   ..XX.   XX...
                                  -----   -----   -----   -OO--
Round 4 (weight 20) after previous χ, then before θ of gap 0, then before χ (8 active rows):
.....   .....   ..X..   X.X..  |  .....   .....   .....   .....  |  .....   .....   .....   .....
.....   .....   ..X..   X....  |  .....   .....   .....   .....  |  .....   .....   .....   .....
..+..   .....   ..X..   X....  |  ..+.X   ...X.   X.XX.   .X...  |  ..+.X   ...X.   X.XX.   .X...
.....   .....   ..X..   XX...  |  .....   ...X.   .....   .....  |  .....   ...X.   .....   .....
.....   .....   ..X..   X....  |  ....X   .....   X.XX.   .X...  |  ....X   .....   X.XX.   .X...
                                  -----   -----   -----   -----
Round 5 (weight 28) after previous χ, then before θ of gap 1, then before χ (12 active rows):
.....   .....   .....   .....  |  ...X.   ....X   .X.XX   .....  |  ...X.   ...XX   XX.XX   .....
.....   .....   .....   .....  |  .....   ...X.   X.XX.   .....  |  .....   .....   ..XX.   .....
..+.X   ...XX   ...X.   .XX..  |  ..+..   .....   .....   ..X..  |  ..+..   ...X.   X....   ..X..
.....   ...XX   .....   .....  |  X....   .X...   X....   X....  |  X....   .X.X.   .....   X....
XX..X   .....   .X.XX   .X...  |  .....   ....X   .....   .....  |  .....   ...XX   X....   .....
                                  O--O-   -O-O-   -OO-O   O-O--

